/// 二维度数组

use std::cmp::{max, min};
use std::mem::swap;
use std::time::Duration;
use crate::multi_tester;
use crate::utils::thread_pool::MultiThreadTester;

/// 旋转矩阵(顺时针90度)
/// https://leetcode-cn.com/problems/rotate-image/
/// 1. 不占用额外内存空间
pub fn rotate_double_dimension_array(matrix: &mut Vec<Vec<i32>>) {
    let len = matrix.len();
    // 首先进行对角呼唤
    for i in 0..len {
        for j in 0..(i + 1) {
            unsafe {
                std::ptr::swap(&matrix[i][j] as *const _ as *mut i32, &matrix[j][i] as *const _ as *mut i32);
            }
        }
    }
    // 然后镜像处理
    for i in 0..len {
        matrix[i].reverse();
    }
}

/// 零矩阵(清除零元素所在的行列：归零)
/// https://leetcode.cn/leetbook/read/array-and-string/ciekh/
pub fn set_zero_in_matrix(matrix: &mut Vec<Vec<i32>>) {
    let len = matrix.len();
    let mut rows = Vec::new();
    let mut cols = Vec::new();
    for i in 0..len {
        for j in 0..matrix[i].len() {
            println!("{},{}", i, j);
            if matrix[i][j] == 0 {
                rows.push(i);
                cols.push(j);
            }
        }
    }
    for x in 0..len {
        if rows.contains(&x) {
            matrix[x].iter_mut().for_each(|e| *e = 0);
        }
        cols.iter().for_each(|e| matrix[x][*e] = 0);
    }
}

/// 对角线遍历
/// https://leetcode.cn/leetbook/read/array-and-string/cuxq3/
pub fn find_diagonal_order(mat: Vec<Vec<i32>>) -> Vec<i32> {
    let mut vec = Vec::new();
    if mat.is_empty() {
        return vec;
    }
    let r = mat.len();
    let c = mat[0].len();
    let m = min(r, c);
    let total_len = r * c;
    vec.reserve(total_len);
    // 遍历次数
    let total_loop = r + c - 1;
    for i in 0..total_loop {
        // 每次遍历的横纵坐标之和i
        let lo = min(m, min(i + 1, r + c - i - 1));
        //确定遍历次数
        if i % 2 == 0 {//偶数左下->右上
            let mut rr = min(r - 1, i);//确定起始r
            for j in 0..lo {
                vec.push(mat[rr - j][i - rr + j]);
            }
        } else {//奇数右上->左下
            let mut rr = min(c - 1, i);//确定起始r
            for j in 0..lo {
                vec.push(mat[i - rr + j][rr - j]);
            }
        }
    }
    vec
}

/// 生成杨辉三角
/// https://leetcode.cn/leetbook/read/array-and-string/cuj3m/
pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
    let mut vec = Vec::new();
    vec.reserve(num_rows as usize);
    vec.push(vec![1]);
    for i in 2..=num_rows as usize {
        let mut tmp = Vec::new();
        for j in 0..i {
            tmp.push(
                if vec![0, i - 1].contains(&j) { 1 } else { vec[i - 2][j] + vec[i - 2][j - 1] }
            );
        }
        vec.push(tmp);
    }

    vec
}

/// 判断杨辉三角第几行数据类型
/// https://leetcode.cn/leetbook/read/array-and-string/ctyt1/
pub fn get_row(row_index: i32) -> Vec<i32> {
    let mut vec = vec![0; row_index as usize];
    vec[0] = 1;
    for i in 2..=row_index as usize {
        for j in (0..i).rev() {
            if j == 0 || j == i - 1 {
                vec[j] = 1;
            } else {
                vec[j] = vec[j] + vec[j - 1];
            }
        }
    }
    vec
}

pub fn get_row_best(row_index: i32) -> Vec<i32> {
    let mut de: i128 = (row_index - 1) as i128;
    let mut nu: i128 = 1;
    let mut vec = vec![1; row_index as usize];
    for i in 1..row_index {
        vec[i as usize] = (de / nu) as i32;
        de *= (row_index - i - 1) as i128;
        nu *= (i + 1) as i128;
    }
    vec
}

/// 获取最小数据
/// 原数组是升序的，但是经过多次旋转后导致顺序位置改变
pub fn find_min(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut left = 0;
    let mut right = n - 1;
    while left < right {
        let mid = left + (right - left) / 2;
        if nums[mid] > nums[right] {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    nums[left]
}

/// 去除非严格递增序列的中的重复元素，同时保证序列的相对顺序
/// https://leetcode.cn/leetbook/read/array-and-string/cq376/
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    if nums.is_empty() { return 0; }
    let mut start = 0;
    for i in 1..nums.len() {
        if nums[i] != nums[start] {
            start += 1;
            nums[start] = nums[i];
        }
    }
    (start + 1) as i32
}

/// 移动零
/// https://leetcode.cn/leetbook/read/array-and-string/c6u02/
pub fn move_zeroes(nums: &mut Vec<i32>) {
    if nums.is_empty() { return; }
    let len = nums.len();
    for i in (0..nums.len() - 1).rev() {
        if nums[i] == 0 {
            unsafe {
                std::ptr::copy(&nums[i + 1] as *const i32, &mut nums[i] as *mut i32, len - i - 1);
                nums[len - 1] = 0;
            }
        }
    }
}

pub fn fast_move_zeroes(nums: &mut Vec<i32>) {
    if nums.is_empty() { return; }
    let len = nums.len();
    let mut p = 0;
    for n in 0..len {
        if nums[n] != 0 {
            nums[p] = nums[n];
            p += 1;
        }
    }
    nums[p..len].iter_mut().for_each(|e| *e = 0);
}


#[test]
fn test_rotate_double_dimension_array() {
    let mut vec1 = vec![
        vec![5, 1, 9, 11],
        vec![2, 4, 8, 10],
        vec![13, 3, 6, 7],
        vec![15, 14, 12, 16],
    ];
    rotate_double_dimension_array(&mut vec1);
    println!("{vec1:?}");
}

#[test]
fn test_set_zero_in_matrix() {
    let mut vec1 = vec![
        vec![0, 1, 2, 0],
        vec![3, 4, 5, 2],
        vec![1, 3, 1, 5],
    ];
    set_zero_in_matrix(&mut vec1);
    println!("{vec1:?}");
}

#[test]
fn test_find_diagonal_order() {
    let mut vec1 = vec![
        vec![0, 1, 2, 0],
        vec![3, 4, 5, 2],
        vec![1, 3, 1, 5],
    ];
    let vec2 = find_diagonal_order(vec1);
    println!("{vec2:?}");
}

#[test]
fn test_generate() {
    multi_tester!({
            let vec1 = get_row(25);
    });


    let mut vec2 = vec![0, 1, 0, 3, 4];
    fast_move_zeroes(&mut vec2);
    println!("{vec2:?}");
}

#[test]
fn tester_generate() {
    let mut tester = MultiThreadTester::new();
    tester.append_test("测试", || {
        std::thread::sleep(Duration::from_secs(1));
    }, 20);

    tester.run();
}